from typing import List


class Solution:
    def maxProfit(self, prices1: List[int]) -> int:
        if len(prices1) <= 1:
            return 0

        prices_uniq = []
        for x in prices1:
            if not prices_uniq or x != prices_uniq[-1]:
                prices_uniq.append(x)

        inf = 10**6
        prices_ext = [inf] + prices_uniq + [-inf]
        prices = []
        for i in range(1, len(prices_ext) - 1):
            if not (prices_ext[i-1] < prices_ext[i] < prices_ext[i+1] or prices_ext[i-1] >= prices_ext[i] > prices_ext[i+1]):
                prices.append(prices_ext[i])

        def get_profits(nums):
            minimum = inf
            max_profit = 0
            profits = []
            for i in range(len(nums)):
                if i % 2 == 0:
                    minimum = min(minimum, nums[i])
                else:
                    max_profit = max(max_profit, nums[i] - minimum)
                    profits.append(max_profit)
            return profits
        left = get_profits(prices)
        right = get_profits([-x for x in prices][::-1])[::-1]
        max_profit = max(x+y for x,y in zip([0] + left, right + [0]))
        return max_profit


def brutal_solve(prices):
    n = len(prices)
    if n <= 1:
        return 0

    result = 0
    for i in range(n-1):
        for j in range(i+1, n):
            result = max(result, prices[j] - prices[i])
    if n >= 4:
        for i in range(n-3):
            for j in range(i+1, n-2):
                for k in range(j + 1, n-1):
                    for w in range(k+1, n):
                        result = max(result, prices[j] - prices[i] + prices[w] - prices[k])
    return result


def test():
    import random
    for _ in range(100000):
        n = random.randint(1, 10)
        prices = [random.randint(0, 9) for _ in range(n)]
        res1 = Solution().maxProfit(prices)
        res2 = brutal_solve(prices)
        if res1 != res2:
            print(prices, res1, res2)
test()
